﻿//class Solution {
//public:
//    int massage(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 1), g(n + 1);
//        //填表
//        for (int i = 1; i <= n; i++)
//        {
//            f[i] = g[i - 1] + nums[i - 1];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n], g[n]);
//    }
//};



//class Solution
//{
//public:
//	TreeNode* pruneTree(TreeNode* root)
//	{
//		if (root == nullptr) return nullptr;
//		root->left = pruneTree(root->left);
//		root->right = pruneTree(root->right);
//		if (root->left == nullptr && root->right == nullptr && root->val == 0)
//		{
//			delete root; // 防⽌内泄漏
//			root = nullptr;
//		}
//		return root;
//	}
//};



//class Solution
//{
//	long prev = LONG_MIN;
//public:
//	bool isValidBST(TreeNode* root)
//	{
//		if (root == nullptr) return true;
//		bool left = isValidBST(root->left);
//		// 剪枝
//		if (left == false) return false;
//		bool cur = false;
//		if (root->val > prev)
//			cur = true;
//		// 剪枝
//		if (cur == false) return false;
//		prev = root->val;
//		bool right = isValidBST(root->right);
//		return left && right && cur;
//	}
//};


class Solution
{
public:
	vector<string> ret; // 记录结果
	vector<string> binaryTreePaths(TreeNode* root)
	{
		string path;
		if (root == nullptr) return ret;
		dfs(root, path);
		return ret;
	}
	void dfs(TreeNode* root, string path)
	{
		path += to_string(root->val);
		if (root->left == nullptr && root->right == nullptr)
		{
			ret.push_back(path);
			return;
		}
		path += "->";
		if (root->left) dfs(root->left, path);
		if (root->right) dfs(root->right, path);
	}
};
